//
// Created by Jinyu Zhu on 2022/4/20.
//

#include "algorithm_graph.h"

std::vector<int> AlgorithmUndirectedGraph::Find_neighbor(const PUndirectedGraph& PG, int id)
{
	std::vector<int>neighbor_nodeid;
	UndirectedGraph::Node *node = &(PG->NodeMap[id]);
	for (auto i = 0;i < node->GetDeg();i++) {
		neighbor_nodeid.push_back(node->GetNbrNId(i));
	}
	return neighbor_nodeid;
}

double AlgorithmUndirectedGraph::Evaluate(const PUndirectedGraph& PG, int id, double degree_weight, double value_weight)
{
	//for tagNode
	double score = 100.0;
	UndirectedGraph::Node* node = &(PG->NodeMap[id]);
	//if degree == 1 score == 0
	//
	if (node->GetDeg() == 1)return 0.0;

	// The higher the degree, the lower the score
	// Take the inverse
	double score_degree = (10.0 /double(node->GetDeg()))*degree_weight;
	//The higher the value, the lower the score
	double score_value = (10.0 / double(1.0+node->Value)) * value_weight;
	//others weight
	double score_others = 0.0;
	return score_degree+score_others+score_value;
}


std::vector<int> AlgorithmUndirectedGraph::Find_Topk_neighbor(const PUndirectedGraph& PG, int id, int k, double degree_weight, double value_weight)
{
	std::vector<int> topk_id_vec(k, 0);
	std::priority_queue<std::pair<double,int>,std::vector<std::pair<double,int>>,std::greater<std::pair<double,int>>> q;
	std::vector<int>neighbor_vec = Find_neighbor(PG,id);
	if (neighbor_vec.size() < k)k = neighbor_vec.size();
	if (k == 0)return topk_id_vec;
	for (int i = 0;i < neighbor_vec.size();i++) {
		double score = Evaluate(PG,neighbor_vec[i],degree_weight,value_weight);
		std::pair<double, int> score_id (score,neighbor_vec[i]);
		if (q.size()<k)q.push(score_id);
		else if (q.top().first < score_id.first) {
			q.pop();
			q.push(score_id);
		}
	}
	for (int i = 0; i < k; i++) {
		topk_id_vec[i] = q.top().second;
		q.pop();
	}
	return topk_id_vec;
}

std::vector<int> AlgorithmUndirectedGraph::Find_recommend_path(const PUndirectedGraph& PG, int id, double degree_weight, double value_weight)
{
	std::vector<int>recommend_path_id;
	recommend_path_id.push_back(id);
	int maxpathsize = 4;
	AlgorithmUndirectedGraph::Find_recommend_path_helper(PG,id,recommend_path_id, maxpathsize);
	return recommend_path_id;
}

void AlgorithmUndirectedGraph::Find_recommend_path_helper(const PUndirectedGraph& PG, int id,std::vector<int>&recommend_path_id,int maxpathsize, double degree_weight, double value_weight) {
	if (recommend_path_id.size() == maxpathsize)return;
	std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::less<std::pair<double, int>>> q;
	//find tagNode
	std::vector<int> neighbor_vec = AlgorithmUndirectedGraph::Find_neighbor(PG,id);
	for (int i = 0;i < neighbor_vec.size();i++) {
		double score = Evaluate(PG,neighbor_vec[i], degree_weight, value_weight);
		std::pair<double, int> score_id(score, neighbor_vec[i]);
		q.push(score_id);

	}
	std::vector<int> top_vec;
	while (!q.empty()) {
		std::vector<int>::iterator it = std::find(recommend_path_id.begin(), recommend_path_id.end(), q.top().second);
		if (it != recommend_path_id.end()) {
			q.pop();
		}
		else {
			top_vec.push_back(q.top().second);
			q.pop();
		}
	}
	if (top_vec.size() <= 0)return;
	recommend_path_id.push_back(top_vec[0]);
	std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::less<std::pair<double, int>>> log_q;
	//find LogNode
	std::vector<int> logneighbor_vec = AlgorithmUndirectedGraph::Find_neighbor(PG,top_vec[0]);
	for (int i = 0;i < logneighbor_vec.size();i++) {
		//need to evaluate for lognode
		//todo:
		double score = Evaluate(PG,logneighbor_vec[i], degree_weight, value_weight);
		std::pair<double, int> score_id(score, logneighbor_vec[i]);
		log_q.push(score_id);
	}
	std::vector<int> logtop_vec;
	while (!log_q.empty()) {
		std::vector<int>::iterator it = std::find(recommend_path_id.begin(), recommend_path_id.end(), log_q.top().second);
		if (it != recommend_path_id.end()) {
			log_q.pop();
		}
		else {
			logtop_vec.push_back(log_q.top().second);
			log_q.pop();
		}
	}
	if (logtop_vec.size() <= 0)return;
	recommend_path_id.push_back(logtop_vec[0]);
	Find_recommend_path_helper(PG,logtop_vec[0], recommend_path_id, maxpathsize);
}


